package com.lsa.iview.lists;

import java.util.Comparator;
import java.util.List;

import com.lsa.iview.lists.SingeLinkedList.Node;

public final class SingeLinkedListUtils {
	public static <E> int count(SingeLinkedList<E> l, E element, Comparator<E> c) {
		int count = 0;
		for (E e : l) {
			if (c.compare(e, element) == 0) {
				++count;
			}
		}
		
		return count;
	}
	
	public static <E> SingeLinkedList<E> shuffleMerge(SingeLinkedList<E> l1, SingeLinkedList<E> l2) {
		SingeLinkedList<E> r = new SingeLinkedList<E>();
		Node<E> lastNode = null;
		
		int selector = !l1.isEmpty()? 0 : 1;
		
		while(!l1.isEmpty() || !l2.isEmpty()) {
			Node<E> n = null;
			if (!l1.isEmpty() && selector == 0) {
				n = l1.pop();
			}
			
			if (!l2.isEmpty() && selector == 1) {
				n = l2.pop();
			}
			
			if (n != null) {
				if (lastNode == null) {
					r.append(n);
				}
				else {
					lastNode.next = n;
				}
				lastNode = n;
				lastNode.next = null;
			}
			
			selector = (selector + 1) % 2;
		}
		
		return r;
	}
	
	public static <E> SingeLinkedList<E> mergeSort(SingeLinkedList<E> l, Comparator<E> c) {
		if (l.isTrivial()) {
			return l;
		}

		List<SingeLinkedList<E>> lists = l.frontBackSplit();
		SingeLinkedList<E> l1 = lists.get(0);
		SingeLinkedList<E> l2 = lists.get(1);
		
		l1 = mergeSort(l1, c);
		l2 = mergeSort(l2, c);
		
		return merge(l1, l2, c);
	}
	
	public static <E> SingeLinkedList<E> merge(SingeLinkedList<E> l1, SingeLinkedList<E> l2, Comparator<E> c) {
		SingeLinkedList<E> r = new SingeLinkedList<E>();
		
		Node<E> lastNode = null;
		
		while(!l1.isEmpty() || !l2.isEmpty()) {
			Node<E> n = null;
			
			if (!l1.isEmpty() && !l2.isEmpty()) {
				Node<E> n1 = l1.firstNode();
				Node<E> n2 = l2.firstNode();
				
				if (c.compare(n1.data, n2.data) <= 0) {
					n = l1.pop();
				}
				else {
					n = l2.pop();
				}
			}
			else {
				if (!l1.isEmpty()) {
					n = l1.pop();
				}
				if (!l2.isEmpty()) {
					n = l2.pop();
				}
			}
			
			if (n != null) {
				if (lastNode == null) {
					r.append(n);
				}
				else {
					lastNode.next = n;
				}
				lastNode = n;
				lastNode.next = null;
			}
		}
		return r;
	}
	
	public static <E> SingeLinkedList<E> sortedIntersect(SingeLinkedList<E> l1, SingeLinkedList<E> l2, Comparator<E> c) {
		SingeLinkedList<E> r = new SingeLinkedList<E>();
		
		if (l1.isEmpty() || l2.isEmpty()) {
			return r;
		}
		
		Node<E> n1 = l1.firstNode();
		Node<E> n2 = l2.firstNode();
		
		Node<E> resultNode = null;
		
		while(n1 != null && n2 != null) {
			int cmp = c.compare(n1.data, n2.data);
			if (cmp < 0) {
				n1 = n1.next;
			}
			else if (cmp > 0) {
				n2 = n2.next;
			}
			else {
				Node<E> tmpNode = new Node<E>(n1.data);
				if (resultNode == null) {
					resultNode = tmpNode;
					SingeLinkedList.add(r, resultNode);
				}
				else {
					resultNode.next = tmpNode;
					resultNode = tmpNode;
				}
				n1 = n1.next;
				n2 = n2.next;
			}
		}
		
		return r;
	}
	
	public static <E> Node<E> reverse(Node<E> head) {
		if (head == null) {
			return head;
		}
		
		Node<E> prev = head;
		Node<E> cur = head.next;
		while(cur != null){
			Node<E> tmp = cur.next;
			cur.next = prev;
			prev = cur;
			cur = tmp;
		}
		head.next = null;
		head = prev;
		
		return head;
	}
	
	/**
	 * ['A', 'B', 'C', 'D'] -> ['A', 'B', 'C', 'D', 'C', 'B', 'A']
	 * @return
	 */
	public static <E> SingeLinkedList<E> appendNMinusOneElementsInReverseOrder(SingeLinkedList<E> l) {
		Node<E> cur = l.firstNode();
		if (cur == null || cur.next == null) {
			return l;
		}
		Node<E> appendCur = null;
		Node<E> appendPrev = null;
		while(cur.next != null) {
			appendCur = new Node<E>(cur.data);
			appendCur.next = appendPrev;
			appendPrev = appendCur;
			cur = cur.next;
		}
		cur.next = appendCur;
		return l;
	}
	
	/**
	 * ['A', 'B', 'C', 'D'] -> ['A', 'B', 'C', 'D', 'C', 'B', 'A']<br>
	 * Slower version
	 * @return
	 */
	public static <E> SingeLinkedList<E> appendNMinusOneElementsInReverseOrder2(SingeLinkedList<E> l) {
		if (l.firstNode() == null || l.firstNode().next == null) {
			return l;
		}
		Node<E> cur = l.firstNode();
		cur = cur.next;
		while(cur.next != null) {
			cur = cur.next;
		}
		Node<E> mid = cur;
		Node<E> front = mid;
		
		cur = l.firstNode();
		while(cur != mid) {
			front.next = new Node<E>(cur.data);
			cur = cur.next;
			front = front.next;
		}
		mid.next = SingeLinkedListUtils.reverse(mid.next);
		return l;
	}
	
	private SingeLinkedListUtils(){
	}
}
